// BTreeMaxPathSum.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <Windows.h>
/* 
Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6. 
*/


struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxPathSum(TreeNode *root) 
{
    int nMaxSum = INT_MIN;
	if(root == NULL) return nMaxSum;
	nMaxSum = root->val;
	int nMaxLeft = 0;
	int nMaxRight = 0;

	int nTemp;
	if(root->left)
    {
        nMaxLeft= maxPathSum(root->left);
       
    }
		
	if(root->right)
    {
        nMaxRight= maxPathSum(root->right);
       
    }

	 nTemp = max(nMaxSum, max((nMaxLeft+nMaxSum), (nMaxRight+nMaxSum)));

		
	 nMaxSum = max(nMaxSum, max(nTemp, (nMaxLeft + nMaxRight+nMaxSum)));
	return nMaxSum;
	
}


int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

